// Created by WXX on 2021/10/7 10:16
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

/**
 * 执行用时：48 ms, 在所有 C++ 提交中击败了12.21%的用户
 * 内存消耗：20.9 MB, 在所有 C++ 提交中击败了10.57%的用户
 */
class Solution {
public:

    bool check(unordered_map<char, int> &a, unordered_map<char, int> &b) {
        for (auto &[k, v] : b)
            if (a[k] < v)
                return false;
        return true;
    }

    string shortestCompletingWord(string licensePlate, vector<string>& words) {
        unordered_map<char, int> T;
        for (auto c : licensePlate)
            if (c != ' ' && !isdigit(c))
                T[tolower(c)]++;

        string res;
        for (auto &w : words) {
            unordered_map<char, int> cnt;
            for (auto c : w) cnt[c]++;
            if (check(cnt, T)) {
                if (res.empty() || res.size() > w.size())
                    res = w;
            }
        }
        return res;
    }
};

int main() {

    vector<string> words = {"step", "steps", "stripe", "stepple"};
    cout << Solution().shortestCompletingWord("1s3 PSt", words) << endl;  // steps

    return 0;
}
